This application is a 371 of PCT/JP98/05027 filed on Nov. 09, 1998.
The present invention generally relates to an interleaving technology for improving error correction ability of an error correction code for burst error. More particularly, the present invention relates to an interleaving method, an interleaving device, and a medium which stores an interleaving pattern generating program for improving the effect of the interleaving by increasing the degree of data randomizing.
In digital transmissions of such as a mobile communications system, the level of received signals varies largely over time by a multipath fading caused by reflections from a building and the like. Therefore, a digital error, such as a burst error, may occur. In addition, in a storing medium of digital systems, such as a compact disc or a hard disk, a digital error such as a burst error may occur due to a scratch, dust or the like on the reading surface of the medium. Thus, various error correction codes are used by various systems. In such an error correction code, for improving the correction ability with respect to the burst error, an interleaving technology is used in concert with the error correction code. The correction ability of the error correction code when a burst error exists depends on the interleaving technology.
In addition, a turbo encoder which uses a high-ability error correction code which has been proposed in recent years includes a plurality of encoders, and each encoder is connected to each other through an interleaver (which carries out interleaving processing), for decreasing the degree of correlation of redundancy system between the encoders. The interleaver is very important for determining the ability of the turbo code.
Therefore, an interleaving method applicable for turbo encoding and transmission systems such as the above-mentioned mobile communication systems using the above mentioned interleaver are required.
As is well known to a person skilled in the art, the purpose of the interleaving method is to randomize the bit sequence of an input bit series and the bit sequence of an out put bit series. The following viewpoint can be used as criteria for evaluating the ability of the interleaving method.
(1) How far apart two successive input bits can be separated in the output series.
(2) How far apart two successive output bits are separated in the input series.
FIG. 1 shows a block interleaving method as a conventional interleaving method.
As shown in FIG. 1, data 100 of one frame includes 1152 bits. A matrix 110 has a buffer of Nxc3x97M (N rows and M columns). The interleaving method is realized such that M bit data is written in the direction of the row, for example, like a vector 115 shown as a diagonally shaded area A, and N bit data is read out in the direction of the column shown as a diagonally shaded area B. By evaluating the interleaving method in terms of the above mentioned criteria, it is recognized that
(1) two successive input bits can not be separated farther apart than N bits in an interleaved output series 130, and
interleavers generated by repeating the second step once or a plurality of times or from each of interleavers generated by the first step, and outputting a data series.
The above-mentioned invention may be configured such that an interleaving method for inputting a data series of a unit length and outputting an interleaved series of the unit length, includes:
a first step of writing the data series to a first interleaver in one direction;
a second step of reading out column data or row data from the first interleaver, writing the read out data to a second interleaver, which has a size different from a size of the first interleaver, in one direction, and repeating the reading out column data or row data and the writing the read out data column by column or row by row;
repeating a third step of performing the second step wherein each of a plurality of the second interleavers generated by the second step is regarded as the first interleaver, and reading out data from each of interleavers generated by repeating the third step or by performing the second step, and outputting a data series.
The above-mentioned interleaving method may be configured such that an interleaving method for inputting a data series of a unit length and outputting an interleaved series of the unit length, includes:
a first step of writing the data series to a first interleaver in one direction;
a second step of reading out column data or row data from the first interleaver, writing the read out data to a second interleaver, which has a size different from a size of the first interleaver,
(2) two successive output bits are separated as far apart as at least M bits in the input series.
However, in the above-mentioned interleaving method, an input bit series is written in the row direction in order of time in the input bit series, and the written data is read out in the column direction also in order of time in the input bit series. Therefore, data is written/read only once in order of time in each of the processes. Therefore, the effect of the interleaving is low, and the performance of the randomizing is limited to the above-mentioned degree even with the Nxc3x97M buffer.
The present invention is achieved in view of the above-mentioned points. A first objective of the present invention is to provide an interleaving method for improving the effect of the interleaving, comparing with the case of reading and writing one by one in order of time, by applying a process of changing a sequence repeatedly after carrying out a process of reading or writing to a buffer once.
To achieve the above-mentioned objective, according to the present invention, an interleaving method for inputting a data series of a unit length and outputting an interleaved series of the unit length, includes:
a first step of writing data of the data series to a first interleaver, reading out the data column by column or row by row from the first interleaver, and writing the data to a plurality of second interleavers;
a second step of reading out the data from each of the second interleavers, and writing the data to one or a plurality of third interleavers as necessary, and
reading out the data from each of in one direction, and repeating the reading out column data or row data and the writing the read out data column by column or row by row;
a third step of reading out data column by column or row by row from each of interleavers generated by the second step, and writing the data to an interleaver which has a size the same as the size of the first interleaver, and
reading out data from the interleaver generated by the third step, and outputting a data series.
In the above configuration, the interleaving method includes:
a fourth step of performing the second step and the third step wherein the interleaver generated by the third step is regarded as the first interleaver, reading out data from an interleaver generated by repeating the fourth step once or a plurality of times, and outputting a data series.
The interleaving method may be configured such that an interleaving method for inputting a data series of a unit length and outputting an interleaved data series of the unit length, includes:
storing a plurality of interleaving patterns in a table beforehand;
applying one of the interleaving patterns to the input data series by referring to the table and outputting data, and
repeating a step of applying one of the interleaving patterns to the output data, and outputting the interleaved data series.
In the above mentioned configuration, an interleaving pattern is stored in the table according to the interleaving method as claimed in one of claims 1-4.
According to the above mentioned invention, because a process of changing sequence is applied repeatedly after carrying out a process of reading or writing to a buffer once, the effect of interleaving can be improved comparing with the case of reading and writing one by one in order of time.
The second objective of the present invention is to provide an interleaving method for supporting various interleaving flexibly with decreased data amount necessary for the interleaving.
To achieve the above mentioned objectives, according to the present invention, a method for generating an interleaving pattern description of an interleaving pattern for interleaving an input data series of a unit length and outputting an interleaved data series of the unit length, includes:
generating the interleaving pattern description of a third unit by using an interleaving pattern description of a first unit and an interleaving pattern description of a second unit.
The present invention generates an interleaving pattern description of a predetermined length unit by using the interleaving pattern description generation method as claimed in claim 7.
In the above configuration, the interleaving pattern description is an interleaving pattern table or an interleaving pattern equation which describes an interleaving pattern.
The interleaving method of the present invention may be configured such that an interleaving method for inputting a data series of a unit length and outputting an interleaved data series of the unit length, includes:
generating an interleaving pattern description of a third unit by using an interleaving pattern description of a first unit and an interleaving pattern description of a second unit, and
interleaving with the generated interleaving pattern description.
Further, the interleaving method of the present invention may be configured such that an interleaving method for inputting a data series of a unit length and outputting an interleaved data series of the unit length, includes:
calculating interleaving destinations in a series of a third unit with an interleaving pattern description of a first unit and an interleaving pattern description of a second unit, and
interleaving with the result of the calculation.
Further, the interleaving method includes:
generating an interleaving pattern description of a first unit and an interleaving pattern description of a second unit by using the interleaving pattern description generated by the method,
interleaving a data series of a third unit by calculating from the interleaving pattern description of a first unit and the interleaving pattern description of a second unit.
Further, that the interleaving pattern description is an interleaving pattern table or an interleaving pattern equation which describes an interleaving pattern.
According to the above mentioned present invention, by generating the interleaving pattern description, for example, from one interleaving pattern table (in the case of A=B), or from two interleaving pattern tables, an interleaving pattern table which has a larger interleaving length can be generated. Thus, a pattern of a certain interleaving length can be represented by a combination of a plurality of patterns of smaller interleaving lengths. Therefore, memory amount for fixed length patterns can be decreased. For example, conventionally, in the case of using an interleaving pattern table for 1000 bits, a memory for 1000 bits is necessary. According to the present invention, by representing the interleaving pattern table for 1000 bits with a 20 bit interleaving pattern table and a 50 bit interleaving pattern table, the memory can be decreased to an amount for 70 (=20+50) bits. In addition, by representing an interleaving pattern table 900 bits with a 20 bit interleaving pattern tablexc3x97a 50 bit interleaving pattern table, interleaving for 1000 bits and 900 bits are possible without enlarging the fixed length interleaving pattern table.
A method according to the present invention may be configured such that a method for generating an interleaving pattern description of an interleaving pattern for interleaving an input data series of a unit length and outputting an interleaved data series of the unit length, includes:
interpreting an interleaving pattern description language which defines an interleaving pattern, and
generating an interleaving pattern description by using the method as claimed in claim 9 on the basis of the interpretation.
In the above configuration, if an interleaving pattern description corresponding to a part of the interleaving pattern description language is stored, the interleaving pattern description is generated with reference to the stored interleaving pattern description without performing a process corresponding to the part of the interleaving pattern description language, when generating an interleaving pattern.
Further, the interleaving method includes:
interpreting an interleaving pattern description language which defines an interleaving pattern, and
interleaving by the method as claimed in claim 13 on the basis of the interpretation.
In the above configured interleaving method, if an interleaving pattern description corresponding to a part of the interleaving pattern description language is stored, the interleaving pattern description is generated with reference to the stored interleaving pattern without performing a process corresponding to the part of the interleaving pattern description language, when interleaving.
The present invention may be configured such that a method for generating an interleaving pattern description of an interleaving pattern for interleaving an input data series of a unit length and outputting an interleaved data series of the unit length, includes:
determining an interleaving pattern description of a first stage when a unit length is given, and
generating an interleaving pattern description by repeating a process of determining interleaving patterns corresponding to interleavers of a column and a row of a stage after the first stage until reaching any stage or until becoming unable to interleave.
Further, the present invention may be configured such that a method for generating an interleaving pattern description of an interleaving pattern for interleaving an input data series of a unit length and outputting an interleaved data series of the unit length, includes:
checking an interleaving pattern description which is generated;
generating an interleaving pattern description again after changing all or a part of parameters if the result of the checking is unsuccessful, and
repeating the checking and the generation until the result of the checking becomes successful so as to generate an interleaving pattern description which passed the checking.
In the above configured interleaving pattern description generation method, the interleaving pattern description which is generated is an interleaving pattern table or an interleaving pattern equation or an interleaving pattern description language.
According to the above mentioned present invention, various interleaving can be supported flexibly with decreased data amount necessary for the interleaving.
The third objective of the present invention is to provide a method for applying the interleaving method to a transmission system device, a turbo encoder, or the like, and to provide the devices such as the transmission system device and the encoder, and a medium storing an interleaving pattern generating program suitable for a target.
To achieve the above objectives, the present invention may be configured such that a method for generating an interleaving pattern description of an interleaving pattern for interleaving an input data series of a unit length and outputting an interleaved data series of the unit length, includes:
a step of determining, when a unit length is given, the number of rows or columns of a block interleaver corresponding to the unit length by using an interleaving pattern list suitable for a predefined application target and defining the number of columns or rows from the determined number of rows or columns, and
generating an interleaving pattern of the unit length from interleaving patterns obtained by repeating the step until the defined number of columns or the defined number of rows is defined in the interleaving pattern list.
In the above configuration, the method includes:
a first step, which is a process of a first stage, of determining the number of rows or the number of columns of a block interleaver corresponding to a unit length which is given beforehand by a defined number, assuming an interleaving pattern corresponding the defined number as a predefined interleaving pattern, and defining the number of rows by using the determined number of columns or defining the number of columns by using the determined number of rows;
a second step of determining the number of rows or the number of columns of a block interleaver corresponding to the defined number of rows or the defined number of columns by using an interleaving pattern list suitable for predefined application target, and defining the number of columns from the determined number of rows or defining the number of rows from the determined number of columns;
a third step of repeating the second step until an interleaving pattern corresponding to the number of rows or columns exists in the predefined interleaving pattern list;
performing the third step a number of times equal to the number of rows or columns corresponding to the predefined interleaving pattern in the first step, and
generating an interleaving pattern corresponding to the row or the column of a former stage sequentially from an interleaving pattern corresponding to the row and the column which is generated in a final stage.
Further, in the above configuration, the generated interleaving pattern of the unit length is checked and an interleaving pattern of the unit length is generated again according to the result of the checking.
Further, in the above configuration, the application target is turbo code and the number of rows of the first stage is 7.
Further, in the above configuration, the application target is transmission and the number of columns of the first stage is the number of slots of one frame.
According to the above mentioned invention, an interleaving pattern suitable for turbo encoding and a transmission system, and the like.
To achieve the above mentioned objectives, an interleaving device for inputting a data series of a unit length and outputting interleaved data series of the unit length, includes:
means which stores one or a plurality of interleaving patterns in a table beforehand;
means which outputs data by applying one of the plurality of interleaving patterns, and
means which outputs the output data by further applying one of the plurality of interleaving patterns as necessary.
In the above configuration, the table stores an interleaving pattern by the interleaving method as claimed in one of claims 1-4.
Further, in the above configuration, the interleaving pattern is generated by the interleaving pattern generating method as claimed in claim 21.
Further, in the interleaving device, interleaving destinations of an input data series are calculated, and the interleaving is performed on the basis of the calculation and data is output instead of using an interleaving pattern.
According to the above mentioned invention, a device for carrying out interleaving processes can be provided, particularly, a device suitable for turbo encoding and transmission, and the like.
To achieve the above mentioned objectives, according to the present invention, a computer readable medium storing a program for description and generation of an interleaving pattern in an interleaving method for inputting a data series of a unit length and outputting an interleaved series of the unit length, includes:
a step of determining the number of rows or columns of a block interleaver corresponding to a unit length which is given beforehand by using an interleaving pattern list suitable for a predefined application target and defining the number of columns from the determined number of rows or the number of rows from the determined number of columns, and
generating an interleaving pattern of the unit length from interleaving patterns obtained by repeating the step until the defined number of columns or the defined number of row is defined in the interleaving pattern list.
Further, in the above configuration, the program includes:
a first step, which is a process of a first stage, of determining the number of rows or the number of columns of a block interleaver corresponding to a unit length which is given beforehand by a defined number, assuming an interleaving pattern corresponding the defined number as a predefined interleaving pattern, and defining the number of rows by using the determined number of columns or defining the number of columns by using the determined number of rows;
a second step of determining the number of rows or the number of columns of a block interleaver corresponding to the defined number of rows or the defined number of columns by using an interleaving pattern list suitable for a predefined application target, and defining the number of columns from the determined number of rows or defining the number of rows from the determined number of columns;
a third step of repeating the second step until an interleaving pattern corresponding to the number of rows or columns exists in the predefined interleaving pattern list;
performing the third step a number of times equal to the number of rows or columns corresponding to the predefined interleaving pattern in the first step, and
generating an interleaving pattern corresponding to the row or the column of a former stage sequentially from an interleaving pattern corresponding to the row and the column which is generated in a final stage.
In the above configuration, in the computer readable medium storing a program for generation of an interleaving pattern of the present invention, the generated interleaving pattern of the unit length is checked and an interleaving pattern of the unit length is generated again according to the result of the checking.
Further, in the computer readable medium storing a program for generation of an interleaving pattern of the present invention, the application target is turbo code and the number of rows of the first stage is 7.
Further, in the computer readable medium storing a program for generation of an interleaving pattern of the present invention, the application target is transmission and the number of columns of the first stage is the number of slots of one frame.
According to the above mentioned invention, a medium storing a program for generating an interleaving pattern can be provided, particularly, a medium storing a program for generating an interleaving pattern suitable for turbo encoding, transmission and the like can be provided.